众所周知，朴素的状压 DP 是 O(2n)O(2^n)O(2n) 起步的，非常慢。
我们可以按照折半搜索（Meet-in-the-Middle）的思想，只枚举所有 111 的位不超过 ⌈n2⌉\lceil\frac{n}{2}\rceil⌈2n ⌉ 的数，然后两两结合就行了。
例如最短 Hamilton 距离我们多开一维表示起始位置，按上面的方法处理出这些 DP，最后不是要求状态为 2n−12^n-12n−1 的最小值吗，我们只需要枚举所有 111 的位不超过 ⌈n2⌉\lceil\frac{n}{2}\rceil⌈2n ⌉ 的 kkk，找到 dp[1][k][i]dp[1][k][i]dp[1][k][i] 与 dp[i][2n−k−1][j]dp[i][2^n-k-1][j]dp[i][2n−k−1][j] 的和的最小值就行了。
注意到这样子总状态数量为 (n1)+(n2)+(n3)+...+(n⌈n2⌉){n\choose 1}+{n\choose 2}+{n\choose 3}+...+{n\choose \lceil\frac{n}{2}\rceil}(1n )+(2n )+(3n )+...+(⌈2n ⌉n )，
显然远远小于朴素状压的 (n1)+(n2)+(n3)+...+(nn−1)+(nn){n\choose 1}+{n\choose 2}+{n\choose 3}+...+{n\choose n-1}+{n\choose n}(1n )+(2n )+(3n )+...+(n−1n )+(nn ) 状态数量。
